package com.breeze.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉链表树,包含二叉树的递归遍历及非递归遍历
 */
class BinaryTree {
    private Node root;
    private int index = -1;

    public boolean isEmpty() {
        return root == null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * 默认前序创建二叉树
     * ABD###C#E## #表示空结点
     */
    public void createBinaryTree(String[] treeDatas) {
        if (treeDatas == null) {
            return;
        }
        root = createTree(treeDatas);
    }

    private Node createTree(String[] treeDatas) {
        index++;
        if (treeDatas[index].equals("#")) { // 空节点
            return null;
        }
        Node node = new Node(treeDatas[index]); // 根
        node.left = createTree(treeDatas); // 左
        node.right = createTree(treeDatas); // 右
        return node;
    }

    /**
     * 前序遍历(递归)
     */
    public void showPreOrder() {
        if (root == null) return;
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value + ",");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 先序遍历(非递归),LeetCode144
     */
    public void showPreOrderUnRecur() {
        // 栈中只保存右子树
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            System.out.print(root.value + ",");
            if (root.right != null) {
                stack.push(root.right);
            }
            root = root.left;
            if (root == null && !stack.isEmpty()) {
                root = stack.pop();
            }
        }
    }


    /**
     * 中序遍历(递归)
     */
    public void showMiddleOrder() {
        if (root == null) {
            return;
        }
        middleOrder(root);
    }

    private void middleOrder(Node node) {
        if (node == null) {
            return;
        }
        middleOrder(node.left);
        System.out.print(node.value + ",");
        middleOrder(node.right);
    }

    /**
     * TODO: 后序遍历(非递归),LeetCode145
     */
    public void showMiddleOrderUnRecur() {

    }


    /**
     * 后序遍历(递归)
     */
    public void showPostOrder() {
        if (root == null) {
            return;
        }
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value + ",");
    }

    /**
     * TODO: 后序遍历(非递归),LeetCode145
     */
    public void showPostOrderUnRecur() {

    }


    /**
     * 层序遍历
     */
    public void showLevelOrder() {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value + ",");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 获取树的深度
     */
    public int getDepth() {
        return getDepth(root);
    }

    private int getDepth(Node node) {
        if (node == null) return 0;
        // 左子树深度
        int lDepth = getDepth(node.left);
        // 右子树深度
        int rDepth = getDepth(node.right);
        // 左右子树最大深度+1(根节点)即为当前树深度
        return Math.max(lDepth, rDepth) + 1;
    }

    class Node {
        String value;
        Node left, right;

        public Node(String value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        /**
         *              A
         *           B      C
         *         D   #  E   F
         *        # #    # # # #
         */
        binaryTree.createBinaryTree(new String[]{"A", "B", "D", "#", "#", "#", "C", "E", "#", "#", "F", "#", "#"}); // 前序
        binaryTree.showPostOrder();
        System.out.println(binaryTree.getDepth());
    }
}

